package oj;

import java.util.ArrayList;
import java.util.List;

public class LC1524 {
    //动态规划
    public int numOfSubarrays(int[] arr) {
        int modi=1000000007;
        int n=arr.length;
        int[][] dp=new int[n][2];
        if(arr[0]%2==0){
            dp[0][1]=1;
        }else{
            dp[0][0]=1;
        }
        for(int i=1;i<n;i++){
            if(arr[i]%2==0){
                dp[i][0]=dp[i-1][0];
                dp[i][1]=dp[i-1][1]+1;
            }
            if(arr[i]%2==1){
                dp[i][0]=dp[i-1][1]+1;
                dp[i][1]=dp[i-1][0];
            }
        }
        int sum=0;
        for(int[] k:dp){
            sum=(sum+k[0])%modi;
        }
        return sum;
    }
    //前缀和+数学:偶-奇=奇，奇-偶=奇
//    public int numOfSubarrays(int[] arr) {
//        int ans=0;
//        int sub=0;
//        int odd=0;
//        int even=1;
//        final int modi=1000000007;
//        for(int i=0;i<arr.length;i++){
//            ans+=arr[i];
//            sub=(sub+(ans%2==0?odd:even))%modi;
//            if(ans%2==0){
//                even++;
//            }else{
//                odd++;
//            }
//        }
//        return sub;
//    }
}
